package com.fanshuai.bitmap.bloomfilter;

/**
 * 布隆过滤器  本质上是一个位图
 * 布隆过滤器用于判断字符串是否重复，例如判断爬虫url是否已经爬取过
 *
 * 布隆过滤器通过计算字符串的k个hash值，将hash值的位图位置设置为1.判断元素存在时，判断相应位置是否为1即可
 */
public class BloomFilter implements IBloomFilter {
    private static final int defaultSize = 1 << 24;
    private static final int[] seeds = new int[] {7, 11, 13, 31, 37, 61};

    private long[] arr;
    private SimpleHash[] func = new SimpleHash[seeds.length];

    public BloomFilter() {
        arr = new long[defaultSize];
        for (int i = 0; i < func.length; i++) {
            func[i] = new SimpleHash(defaultSize, seeds[i]);
        }
    }

    /**
     * 获取>=size的最小2的指数
     * @param size
     * @return
     */
    public int get2Exp(int size) {
        int exp2 = 1;
        while (exp2 < size) {
            exp2 *= 2;
        }
        return exp2;
    }

    public BloomFilter(int size) {
        size = get2Exp(size);
        arr = new long[size];
        for (int i = 0; i < func.length; i++) {
            func[i] = new SimpleHash(size, seeds[i]);
        }
    }

    @Override
    public void add(String v) {
        for (int i = 0; i < func.length; i++) {
            int hash = func[i].hash(v);

            int index = hash >> 6;
            long bit = hash & 63;
            arr[index] |= (1L << bit);
        }
    }

    @Override
    public boolean contains(String v) {
        boolean exists = true;
        for (int i = 0; i < func.length; i++) {
            int hash = func[i].hash(v);

            int index = hash >> 6;
            long bit = hash & 63;

            boolean b = (arr[index] & (1L << bit)) > 0;
            exists = exists && b;
        }

        return exists;
    }
}
